#include <string>
#include <iostream>
#include "albero.h"

using namespace std;

//output file stream
//ofstream f("pippo.txt");

Nodo* Albero::getRoot(){
    return root;
}

void  Albero::divtre(){
  divtre(root,0);
}

void  Albero::divtre(Nodo* x, int r){

        Residuo *y,*z,*xe,*ye;
        string ftp = x->fattore;
        int lg = ftp.length();
        int rx = x->resto;
        // ftp = fattore precedente
        // lg = lunghezza fattore precedente
        // rx = [[ftp]]

        // triplico il fattore
        string rst,ft = ftp+ftp+ftp;
        // ft = fattore precedente triplicato
        // lo divido per 3 tenendo conto del resto r precedente
        // e calcolo rf = [[ft]]
        string::iterator i;
        int rs=r, rf=0, q, j;
        for (i=ft.begin(); i<ft.end();i++){
                rs = *i-'0'+2*rs;
                q=rs/3;
                rs = rs%3;
                *i= char(q+'0');
                rf=(q+2*rf)%3;
                //cout<<rf<<" ";
        } //cout<<endl;

        // aggiorno il fattore e il suo resto
        x->fattore=ft;
        x->resto=rf;
        // aggiorno la lista dei resti iniziali usati
        x->resti = char(r+'0')+x->resti;

        // aggiunge il multiplo 0 ai residui
        y = x->residui;
        while(y != NULL){
        y->multipli.push_back('0');
        y=y->succ;
        }

        /* aggiunge in coda alla lista dei residui due copie di tale lista
         una con lunghezze aumentate di lg, resto aumentato di rx, multipli+1
         una con lunghezze aumentate di 2*lg e resto aumentato di 2*rx, multipli+2
        */

        copia(x->residui,y,xe,lg,rx);
        copia(y,z,ye,lg,rx);
        xe->succ=y;
        ye->succ=z;

        y = x->residui;

        if (y->continuazione != NULL)
                while (y != NULL) { // se ci sono continuazioni le divido per 3
                  rs = y->lunghezza%2==0?r:2*r;
                  divtre(y->continuazione,(rs+y->resto)%3);
                  y = y->succ;
                }

        else {
        // elimino i residui con resto 0, aggiungo [10]1 a quelli con resto 2
        // e [01]01 a quelli con resto 1
                z = NULL;
                while (y != NULL){
                        rs = y->lunghezza%2==0?r:2*r;

                        switch ((rs+y->resto)%3) {

                        case 0: // lo elimino dalla lista
                                if (z == NULL) { // e' il primo
                                  x->residui=y->succ;
                                  y->succ = NULL;
                                  delete y;
                                  y = x->residui;
                                }
                                else { // non e' il primo
                                  z->succ=y->succ;
                                  y->succ = NULL;
                                  delete y;
                                  y = z->succ;
                                }
                        break;

                        case 1: // aggiungo [01]01
                                //	y->continuazione = new Nodo("01",1,new Residuo(2,1),"1");
                                y->continuazione = new Nodo("01",1,new Residuo(2,1),"1");
                                z = y;
                                y = y->succ;
                        break;

                        case 2: // aggiungo [10]1
                                y->continuazione = new Nodo("10",2,new Residuo(1,1),"2");
                                z = y;
                                y = y->succ;
                        }
                }
        }

        // calcolo i resti dei prefissi del fattore ft e li memorizzo in rst
        rst.push_back(0);
        j=0;

        for (i=ft.begin(); i<ft.end();i++) {
                rst.push_back((*i-'0'+2*rst[j])%3);
                j++;
        }

        // aggiorno i resti della lista dei residui
        y = x->residui;

        while (y != NULL) {
                y->resto = rst[y->lunghezza];
                y = y->succ;
        }
}

void Albero::copia(Residuo* &x, Residuo* &y, Residuo* &xe, int lg, int rx){
  Residuo *z, *xc;
  int r;
  /* effettua una copia della lista dei residui x
     con lunghezze aumentate di lg e resto aumentato di rs
     y e ye sono i puntatori all'inizio e alla fine della nuova lista
  */
  // copia profonda della lista dei residui x
  y=new Residuo(*x);
  // aggiornamento delle lunghezze e dei resti calcolo di xe
  xe=NULL;
  xc = x;
  z = y;
  while (xc != NULL) {
    z->lunghezza = xc->lunghezza+lg;
    r = xc->lunghezza%2==0?rx:2*rx;
    z->resto = (xc->resto+r)%3;
    z->multipli[z->multipli.length()-1]++;
    xe= xc;
    xc= xc->succ;
    z = z->succ;
  }
}

void Albero::step(){
  divtre();
}

void Albero::stepTree(int n) {
  int i;

  //Nodo *x = new Nodo("01",1,new Residuo(2,1),"1");
  //Albero A(x);

  root = new Nodo("01",1,new Residuo(2,1),"1");

  //cout << "npassi = "; cin >> n;
  //f << "npassi = " << n << endl;

  //passo 1
  //cout << "Gruppo 1" << endl;
  //f << "Gruppo 1" << endl;
  //A.scrivi();

  //passi 2+
  for (i=2; i<=n; i++) {
    //A.step();
    divtre();
    //cout << "Gruppo " << i << endl;
    //f << endl << "Gruppo " << i << endl;
    //A.scrivi();
  }

  //return &A;
}
